\section{Approach}

In this section we will take a close look at how we approached this
project. We will discuss our improvements to the algorithms, differences
with the approach used last year and the problems we stumbled upon. Our project
consists of few phases. First we built on the legacy from the team who did
this project last year. We looked at the code and tried to figure out
how it all worked. Then we ported it to other operating systems, and
implemented the genetic algorithms we needed..


\subsection{Observing last year's work}

When we started this project we already had code from last year and we
began by using it and looking at its possibilities. We soon
found out the code would only work under specific circumstances, most
noticeable only on Linux. Since not all of us had a computer running Linux
available when not at university, we figured we had to make it work on
Windows and maybe Mac OS X as well in order to be reasonably productive.

Before doing that however, we dug a little deeper into last year's code and
we got it working on a Linux computer. After reading the paper last year's
team wrote, we figured they had made some significant mistakes in
implementing the genetic algorithms, so we took a specific look at the
genetic part of the code.


\subsection{Improving compatibility}

When we understood the basics of the program we started out to fix the code
to use it on all our operating systems. This proved to be a lot harder than we
thought it would be. Ever since Quake III had been made open source,
volunteers have worked on improving the code for years and a lot had
changed in the past year.  We decided to make a patch for the Quake III
source code to add our own code. This makes sure that when the Quake III code
is updated, everything will still work.
This way, you can always get all the updates on the latest Quake code and
still use our test environment.

Eventually this task took up the entire first week to finish, but we were
quite pleased with the result. We got it working on Linux and Windows
as well, using the newest build version of Quake III. After testing our
new code we unfortunately got hold of a problem which would slow down our
tests significantly. In Quake there is an option called `timescale' to
increase the speed of the game, which we would use to speed up our tests.
When using our new code however, if we increased the speed of the game
all the bots would act very unnatural and would not kill any other bots
at all. Somehow they could not play in an increased timescale. This was
a problem that should definitely be fixed.


\subsection{Genetic algorithms}

We did not really know where to look for the timescale problem and
already lost a lot of time in making the new implementations we divided our
work. Gijs would look into this problem, while Steven and Steijn would
improve last year's genetic algorithms. Niels would then help out where
possible and already start on the final paper.

Soon we realized that it was hard to add functionality to last year's code.
Because of this we started by rewriting the genetic code from last year,
in a way that would suit our new ideas. Luckily this was done in only a
few hours and after fixing some small bugs we were ready to make the
necessary improvements.

Last year, nothing was done to make a distinction between phenotype and
genotype. Naturally this was the first thing to improve. We wrote some code
that would translate genotypes of the bots to their actual phenotype and we
left room for making different dependencies between certain genotypes and
phenotypes. An example of such a dependency: a bot that is very aggressive
will not be a camper, while a less aggressive bot will be more likely to
camp.

Another thing that has been greatly improved is the way parents are chosen
for the new generation and how the genes are inherited. Last year the best
two bots of a round would always be the parents for the next round. Three
new children were created and randomly got genes from either of the
parents. The two parents were also used in the next round as well as a new
completely random bot. This is not how a genetic algorithm is generally
used. Normally no parent is kept for successive rounds. We also found
that the random bot only slows down improvement in genes.

To improve the algorithm we started by removing the random bot, which was
added in every round. We also changed the selection of the parents. We made
what is called a roulette selection. For every bot we will generate a
fitness value, depending on his frags and deaths in a round. The better a
bot has scored, the higher the fitness value will be. Then for every two
children for the next generation we select new parents. A bot who has
scored better, thus having a better fitness value, will be chosen as a
parent more often than a bot with a lower fitness value. But bots with
lower fitness values also have a (small)  chance of becoming a parent.
Parents will not be taken to the next round anymore, instead more children
are created. Lastly the way genes are being inherited is improved using
crossover. This is a more general way of distributing genes from parents
to their children.


\subsection{Testing the algorithm}

Luckily when Steven and Steijn were busy improving the genetic algorithm,
Gijs found how to fix the timescale problem. So it became possible to speed
up our tests, which would otherwise take a very long time - now they took
about 2 hours each instead of 12 hours or so. Because we
changed the way genes are stored and added more characteristics as genes,
we could not use the graphing code that was used last year.
We needed this tool to get a better insight into our test results, so Niels
started to work on a program to visualize our results. Meanwhile Gijs,
Steven and Steijn would optimize the code and start running some tests.

Once the first tests were run and Niels finished his program we could
actually see some results from our work in the form of a graph.

After obtaining some results, we realized that the random mutation was
interfering with the evolutionary process, as bots could either retain
exactly the same value for a characteristic or obtain a completely random
new value for it. So we then implemented a Gaussian (Normal) distribution
for the adjustment of the values. Now they would be very likely to remain
almost the same, and unlikely to shift by a significant amount.

Using this setup we ran several experiments in an attempt to answer our
research questions. The results of these experiments are in section \ref{results}.

